# 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
#  进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
#
#  示例 1：
# 输入：nums = [1,2,1,3,2,5]
# 输出：[3,5]
# 解释：[5, 3] 也是有效的答案。
#
#  示例 2：
# 输入：nums = [-1,0]
# 输出：[-1,0]
from typing import List


class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        """
        位运算
        以[1,2,1,3,2,5]为例
        xorSum = 5 ^ 3 = 6(0b110)  (最终这个结果的二进制为1的位置上x1和x2是不相同的)
        lowBitNum = 2(0b010)

        最后想从xorSum分离出 x1, x2就可以以lowBitNum & num[i] == 0 为分界将数组分成两部分，
        但是由于 a ^ a = 0，也就是那些相同的数字虽然被分成两部分，但是分出的每部分最终都异或得到了0
        那么最终只会有：
            xorSum ^ x1 = x2
            xorSum ^ x2 = x1
        :param nums:
        :return:
        """
        xorsum = 0
        for num in nums:  # 先得到两个结果的异或值 x1 ^ x2
            xorsum ^= num
        # -x 的值， 其实就是在x的值的基础上进行按位取反(~x)之后在增加1所得(x & -x <==> x & (~x + 1))
        lowBitNum = xorsum & (-xorsum)  # 得到x 的二进制表示中最低位那个 1，设其为第 l 位
        x1 = x2 = 0
        # 找到这个第一个不同的位，然后将数组中的数分成两份，该位为0的进行异或求解得到其中一个结果x1，该位为1的进行异或求解得到另一个结果x2
        for num in nums:
            if num & lowBitNum:
                x1 ^= num
            else:
                x2 ^= num

        return [x1, x2]


if __name__ == "__main__":
    nums = [1, 2, 1, 3, 2, 5]
    print(Solution().singleNumber(nums))
